package stack.easy;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 1. 问题描述
 *
 * 2. 算法分析
 *      注意到这一点即可：由于给定的S已经是匹配的括号字符串了，那么如果当前的原子括号的起点入栈
 *      按照括号匹配的方式，当前左括号入栈，当前右括号将栈顶左括号出栈，此时由于S是匹配的，所以
 *      如果当前出栈之后栈为空，说明已经走完了当前的一整个原子括号了
 *
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 删除最外层的括号 {
    public static void main(String[] args) {

    }

    /**
     * 代码中的核心是index索引的含义：永远指向每个原子的括号字符串的起始的下一个括号
     * 所以下面的代码中增加了一个对index的判断，主要是考虑到边界问题
     * @param S
     * @return
     */
    public static String removeOuterParentheses(String S) {
        if(S.length() == 0) {return "";}
        Deque<Character> stack = new ArrayDeque<>(); // 定义栈
        StringBuilder ans = new StringBuilder(); // 存放结果
        stack.push(S.charAt(0)); // 初始化栈 将第一个原子括号的起始放置到栈中
        int index = 1; // 定义指针指向S
        while(!stack.isEmpty() && index < S.length()) { // 当栈不空时
            if(S.charAt(index) == '(') {
                stack.push(S.charAt(index));
                ans.append(S.charAt(index));
                index++;
            } else {
                // 当前为右括号
                stack.pop(); // 出栈
                // 如果出栈之后栈空，说明当前原子括号结束了
                if(stack.isEmpty()) {
                    index++;
                    /**
                     * 注意此时我们 需要添加一个判断
                     */
                    if(index >= S.length()-1) {
                        return ans.toString();
                    }
                    stack.push(S.charAt(index)); // 将下一轮的原子括号的起始入栈
                    index++; // 将下一轮的原子括号的起始入栈此时index需要继续后移一位，从原子括号的内部的第一个括号开始
                    continue;
                }
                ans.append(S.charAt(index));
                index++;
            }
        }
        return ans.toString();
    }
}
